from typing import List


class Solution:
    """
    方法： searchInsert

    逻辑: 使用二分查找在有序数组中寻找目标值的插入位置。如果目标值存在，返回其索引；如果不存在，返回它应该被插入的位置。

    Args:
        nums (List[int]): 有序的整数数组
        target (int): 要查找或插入的目标值

    Returns:
        int: 目标值在数组中的位置或应该插入的位置

    Time:  
        O(log n)，其中 n 是数组的长度。每次迭代将搜索范围缩小一半。

    Space:  
        O(1)，只使用了常数级别的额外空间。
    """
    def searchInsert(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1 #闭区间 [left, right]
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] < target:
                left = mid + 1 #[mid+1, right]
            else:
                right = mid - 1 #[left, mid-1]
        return left

    """
    方法： searchInsert1

    逻辑: 使用二分查找在有序数组中寻找目标值的插入位置。如果目标值存在，返回其索引；如果不存在，返回它应该插入的位置。
    使用开区间(left, right)的二分查找实现。

    Args:
        nums (List[int]): 有序的整数数组
        target (int): 要查找或插入的目标值

    Returns:
        int: 目标值在数组中的位置或应该插入的位置

    Time:  
        O(log n)，其中 n 是数组的长度。每次迭代将搜索范围缩小一半。

    Space:  
        O(1)，只使用了常数级别的额外空间。
    """
    def searchInsert1(self, nums: List[int], target: int) -> int:
        left, right = -1, len(nums) #开区间(-1, n)
        while left + 1 < right:
            mid = (left + right) // 2
            if nums[mid] < target:
                left = mid #(mid, right)
            else:
                right = mid #(left, mid)
        return right

    """
    方法： searchInsert2

    逻辑: 使用二分查找在有序数组中寻找目标值的插入位置。如果目标值存在，返回其索引；如果不存在，返回它应该插入的位置。
    使用左闭右开区间[left, right)的二分查找实现。

    Args:
        nums (List[int]): 有序的整数数组
        target (int): 要查找或插入的目标值

    Returns:
        int: 目标值在数组中的位置或应该插入的位置

    Time:  
        O(log n)，其中 n 是数组的长度。每次迭代将搜索范围缩小一半。

    Space:  
        O(1)，只使用了常数级别的额外空间。
    """
    def searchInsert2(self, nums, target):
        left, right = 0, len(nums) #左开右闭区间[left, right)
        while left < right:
            mid = (left + right) // 2
            if nums[mid] < target:
                left = mid + 1 #[mid+1, right)
            else:
                right = mid  #[left, mid)
        return right
        